590C - Three States - CodeForces Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <iomanip>
#include <iterator>
#include <cmath>
#include <map>
#include <string.h>
#include <ctime>
#include <queue>
#include<unordered_map>
#include<stack>
#include<unordered_set>
#define Tamora ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ld long double
using namespace std;

vector<int>dirx{ 1,-1, 0,0,1,1,-1,-1 };
vector<int>diry{ 0,0,-1,1,1,-1,1,-1 };

bool valid(int n, int m, int x, int y) {
	return x >= 0 && y >= 0 && x < n&& y < m;
}

ll gcd(ll a, ll b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return (a * b) / gcd(a, b);
}

const ll mod = 1e9 + 7, inf = 1e8, N = 1e3 + 5, M = 100 + 5;

string grid[N];
int cost1[N][N], cost2[N][N], cost3[N][N];
int n, m;

void bfs(char start,int cost[N][N]) {
	deque<pair<int, int>>dq;
	int x, y;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cost[i][j] = inf;
			if (grid[i][j] == start)
				x = i, y = j;
		}
	dq.push_back({x,y});
	cost[x][y] = 0;
	while (!dq.empty()) {
		int curx = dq.front().first, cury = dq.front().second;
		int curc = cost[curx][cury];
		dq.pop_front();
		for (int k = 0; k < 4; k++) {
			int x = curx + dirx[k];
			int y = cury + diry[k];
			if (valid(n, m, x, y) && grid[x][y] != '#') {
				if (grid[x][y] == '.') {
					if (cost[x][y] > curc + 1)
						dq.push_back({x,y}), cost[x][y] = curc + 1;
				}
				else
					if (cost[x][y] > curc)
						dq.push_front({x,y}), cost[x][y] = curc;
			}
		}
	}
}
void solve() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> grid[i];

	bfs('1', cost1);
	bfs('2', cost2);
	bfs('3', cost3);
	int ans = inf;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (grid[i][j] == '.')
				ans = min(ans, cost1[i][j] + cost2[i][j] + cost3[i][j] - 2);
			else
				ans = min(ans, cost1[i][j] + cost2[i][j] + cost3[i][j]);
	if (ans >= inf)
		cout << -1 << endl;
	else
		cout << ans << endl;
}



//void files() {
//
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
//}


int main() {
	Tamora;
	/*int t; cin >> t;
	while (t--)*/
		solve();

}